﻿#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"

//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
//有效字符串需满足：
//
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//每个右括号都有一个对应的相同类型的左括号。

bool isValid(char* s) {
    ST stack;
    StackInit(&stack);
    while (*s)
    {
        if (*s == '(' 
            || *s == '{' 
            || *s == '[')
        {
            StackPush(&stack, *s);
            s++;
        }
        else
        {
            //如果遇到右括号了，但是栈为空，说明前面没有右括号入栈，匹配失败
            if (StackEmpty(&stack))
            {
                StackDestroy(&stack);
                return false;
            }
            STDatatype top = StackTop(&stack);
            StackPop(&stack);
            if ((*s == ')' && top != '(')
                || (*s == ']' && top != '[')
                || (*s == '}' && top != '{'))
            {
                StackDestroy(&stack);
                return false;
            }
            else
            {
                s++;
            }
        }
    }
    bool ret = StackEmpty(&stack);
    //如果栈不是空，说明还有左括号未出栈（没被匹配），要返回false
    StackDestroy(&stack);
    return ret;
}
int main()
{
    //测验栈的实现
	/*ST stack;
	StackInit(&stack);
	StackPush(&stack, 1);
	StackPush(&stack, 2);
	StackPush(&stack, 3);
	printf("%d ", StackTop(&stack));
	StackPop(&stack);
	StackPush(&stack, 4);
	StackPush(&stack, 5);
	while (!StackEmpty(&stack))
	{
		printf("%d ", StackTop(&stack));
		StackPop(&stack);
	}
	StackDestroy(&stack);*/

    char arr[50] = { 0 };
    printf("请输入一个只包含'('，')'，'{'，'}'，'['，']' 的字符串：\n");
    gets(arr);
    if (isValid(arr) == 1)
        printf("\n匹配成功!!!\n");
    else
        printf("\n匹配失败!!!\n");
	return 0;
}